package com.atcumt.Carl.Greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Greedy02 {

    /**
     * 无重叠区间
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[1], o2[1])); // 按右边界排序
        int count = 0;
        int rightEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (rightEnd <= intervals[i][0]) {
                rightEnd = intervals[i][1]; // 无重叠
            } else {
                count++; // 有重叠区间，移除
            }
        }
        return count;
    }

    /**
     * 划分字母区间
     * 方法：找每一个字母的边界，找到之前遍历过的所有字母的最远边界，这个边界就是分割点
     */
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        int[] hash = new int[26]; // 记录字符出现位置
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a'] = i; // 统计每一个字符最后出现的位置
        }

        int start = 0;
        int rightEnd = 0; // 已扫描字符最远位置（边界）
        for (int i = 0; i < s.length(); i++) {
            rightEnd = Math.max(rightEnd, hash[s.charAt(i) - 'a']);

            if (i == rightEnd) {
                res.add(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }


    /**
     * 合并区间
     * 方法：处理好三种情况，覆盖、重叠和不重叠
     * List -> Array
     */
    public int[][] merge(int[][] intervals) {
        if (intervals.length < 2) {
            return intervals;
        }

        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0])); // 按左边界排序
        int leftStart = intervals[0][0];
        int rightEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (rightEnd > intervals[i][1]) {
                continue; // 覆盖
            } else if (rightEnd >= intervals[i][0]) {
                rightEnd = intervals[i][1]; // 相交, leftStart不变
            } else if (rightEnd < intervals[i][0]) {
                res.add(new int[]{leftStart, rightEnd}); // 相离
                leftStart = intervals[i][0];
                rightEnd = intervals[i][1];
            }
        }
        // 返回结果 list -> array
        res.add(new int[]{leftStart, rightEnd});
        return res.toArray(new int[res.size()][]);
    }
}
